package main.old.new_2023.last.month_6;

import java.util.*;

/**
 * @Description: //
 * todo 1177. 构建回文串检测
     * 给你一个字符串 s，请你对 s 的子串进行检测。
     * 每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
     * 如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
     * 返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
     * 注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
 *
 *  todo 剑指 Offer 31. 栈的压入、弹出序列
     *  输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
     *  例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0615 {

    //栈的压入、弹出序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //模拟入栈/出栈的流程
        Deque<Integer> stack = new ArrayDeque<>();
        int n = pushed.length;
        for (int i= 0,j=0;i<=n;i++){
            //押入栈
            stack.push(pushed[i]);
            while (!stack.isEmpty()  && stack.peek() == popped[j]){
                //出栈
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    //构建回文串检测
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        int[] count = new int[n + 1];
        for (int i = 0; i < n; i++) {
            count[i + 1] = count[i] ^ (1 << (s.charAt(i) - 'a'));
        }
        List<Boolean> res = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1], k = queries[i][2];
            int bits = 0, x = count[r + 1] ^ count[l];
            while (x > 0) {
                x &= x - 1;
                bits++;
            }
            res.add(bits <= k * 2 + 1);
        }
        return res;

    }


    public static void main(String[] args) {

    }
}
